package leetcode

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func maxDepth1(root *TreeNode) int {
	if root == nil {
		return 0
	}

	l, r := maxDepth1(root.Left), maxDepth1(root.Right)
	if l > r {
		return l + 1
	}
	return r + 1
}

func maxDepth(root *TreeNode) int {
	if root == nil {
		return 0
	}

	q, next, n, depth, i := []*TreeNode{root}, make([]*TreeNode, 0, 2), new(TreeNode), 1, 0
	for {
		n, i = q[i], i+1

		if n.Left != nil {
			next = append(next, n.Left)
		}
		if n.Right != nil {
			next = append(next, n.Right)
		}

		if i < len(q) {
			continue
		}

		if len(next) == 0 {
			break
		}

		q, next, depth, i = next, q[:0], depth+1, 0
	}

	return depth
}
